The present invention is related to the field of overlay networks, and more particularly to routing-related operation of overlay networks.
In an overlay network, routing is required to locate a node or a group of nodes (e.g. a LAN) that are responsible for a portion of a “key space” used to distribute data among the nodes of the overlay network. Existing routing approaches in overlay networks rely on logical relationships in the overlay network. For example, a hash key calculated from data or metadata may be used as the basis of routing decisions. To locate a node or group of nodes that are responsible for a particular hash key (also referred to herein as “key” or “key value”), the routing process may compare the hash key with hashes of logical node identifiers, which in general provide no information about connections or other relationships among the nodes in the underlying physical network. The lack of such information may lead to non-optimal data placement and network operation. These kinds of overlay networks may be termed “topology unaware”.
Certain improvements in overlay network design may better align hash key space with physical network topology, but still rely on the abstract key space as the main factor in routing decisions. There are several disadvantages of these approaches. For example, logical key space cannot be accurately aligned with physical network topology; therefore there is always the issue of logical space mismatch with physical network topology, resulting in long routing delays. Additionally, as the network size increases, the logical space is further divided into smaller regions, and the routing process will take more steps and therefore introduce longer delays.